import java.util.*;

public class Solution827 {
    int[][] grid;
    int m, n;
    int[][] directArr = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    boolean[][] isBeen;

    private boolean checkBound(int i, int j){
        return !(i < 0 || m <= i || j < 0 || n <= j);
    }

    private int getArea(int i, int j, int ind){
        if(!checkBound(i, j) || isBeen[i][j] || grid[i][j] == 0){
            return 0;
        }
        grid[i][j] = ind;
        isBeen[i][j] = true;
        int res = 1;
        for (int[] direct : directArr) {
            int newI = i + direct[0], newJ = j + direct[1];
            res += getArea(newI, newJ, ind);
        }
        return res;
    }

    public int largestIsland(int[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        this.isBeen = new boolean[m][n];
        Map<Integer, Integer> indAreaMap = new HashMap<>();
        int maxArea = 0;
        int ind = 2;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 1){
                    int area = getArea(i, j, ind);
                    indAreaMap.put(ind++, area);
                    maxArea = Math.max(maxArea, area);
                }
            }
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 0){
                    Set<Integer> indSet = new HashSet<>();
                    for (int[] direct : directArr) {
                        int newI = i + direct[0], newJ = j + direct[1];
                        if(checkBound(newI, newJ)){
                            indSet.add(grid[newI][newJ]);
                        }
                    }
                    int area = 1;
                    for (Integer tmpInd : indSet) {
                        area += indAreaMap.getOrDefault(tmpInd, 0);
                    }
                    maxArea = Math.max(maxArea, area);
                }
            }
        }
        return maxArea;
    }

    public static void main(String[] args) {
        Solution827 s = new Solution827();
        s.largestIsland(new int[][]{{1,1},{1,0}});
    }
}
